#include "Link.h"


LinkNode::LinkNode(int dat, LinkNode *n)
{
    data = dat;
    next = n;
}

LinkNode * generateLink(int len)
{
    LinkNode * header = new LinkNode(generateRandom(), NULL);
    LinkNode * curNode = header;
    while (--len)
    {
        curNode->next = new LinkNode(generateRandom(), NULL);
        curNode = curNode->next;
    }

    curNode->next = NULL;
    
    return header;
}

/*
 * 判断一个单向链表是不是有环.
 *
 * 环路单身链表,找到交叉的地方.
 * 两个索引进行遍历,一个一次前进一步,一个一次前进两步, 当前进一两步的赶上前进一步,那么肯定是有环的.
 */
LinkNode * getIntersectNode(LinkNode * link)
{
    LinkNode * LINK = NULL;
    LinkNode * oneIdx = link; 
    LinkNode * twoIdx = link; 

    if(link == NULL || link -> next == NULL)
        return NULL;

    while(twoIdx != NULL && twoIdx->next != NULL)
    {
        twoIdx = twoIdx->next;
        twoIdx = twoIdx->next;

        //one moves slow, so it can't be possible equals null.
        oneIdx = oneIdx->next;
#if 0
        if(twoIdx == oneIdx || (twoIdx && twoIdx -> next == oneIdx))
        {
            std::cout << "we have loops in our link" ;
            std::cout << " contain " << twoIdx->data << " and " <<  twoIdx->next->data << std::endl;
            //broken down the loop, we get two links.
            LINK = twoIdx->next;
            twoIdx->next = NULL;
            break;
        }
#endif
        if(twoIdx == oneIdx )
        {
            std::cout << "we have loops in our link" ;
            std::cout << " contain " << twoIdx->data << std::endl;
            //broken down the loop, we get two links.
            LINK = twoIdx;
            break;
        }
    }

    if(LINK == NULL)
    {
        std::cout << "we don't  have loops in our link" ;
        return NULL;
    }

    oneIdx = link;
    
    while( oneIdx != twoIdx)
    {
        oneIdx = oneIdx -> next;
        twoIdx = twoIdx -> next;
    }

    std::cout << "The crossNode is " << oneIdx ->data << std::endl;

    return NULL;
}

/*
 * 有两个单向链表,表头pHeader1,pHeader2,请写一个函数判断这两个链表是否有交叉.如果有交叉,给出交叉点.
 * 程序不能改变链表的内容,可以使用额外的空间,时间复杂度尽量小,最好给出两种解.(双重循环的解由于时间复杂度高，不算正解).
 *  
 *  基本思想：如果两个链表交叉，那么这两个链表在交叉点之后的节点是完全相同的！！
 *  因此可以用一下的算法判断两个链表是否交叉
 *  1. 分别得到两个链表的最后一个节点,以及链表的长度. 
 *  2. 如果2个链表的最后一个节点地址相同,则有交叉,否则执行3
 *  3.
 *  假设两个链表的长度分别是m和n,且m>=n,那么移动长的那个链表，先移动m-n个节点，是长链表与短链表在末端对齐，然后从对其的节点开
 *  始比较两个链表，如果不相等,就都向后移动一格.（注意这里是两个链表的指针同时向后移动）直到相等,相等的节点就是交叉点.
 *  4. 时间复杂度O(n+m).
 */
LinkNode * getIntersectNode(LinkNode * link1, LinkNode * link2)
{
    if(link1 == NULL || link2 == NULL)
        return NULL;

    if(link1 == link2)
        return link1;

    LinkNode *link1Idx = link1;
    
    LinkNode *link2Idx = link2;

    int len1 = 0;
    int len2 = 0;

    //link1Idx points to last element.
    while(link1Idx != NULL && link1Idx -> next != NULL)
    {
        link1Idx = link1Idx->next;
        len1++;
    }
    len1++;

    //link2Idx points to last element.
    while(link2Idx != NULL && link2Idx -> next != NULL)
    {
        link2Idx = link2Idx->next;
        len2++;
    }
    len2++;


    std::cout<< "Link1 len is "<< len1 << " Link2 len is " << len2 << std::endl;

    if(link1Idx == link2Idx)
        std::cout << "there are intersect node" << std::endl;

    //get the cross point.
    link1Idx = link1;
    link2Idx = link2;
    if(len1 > len2)
    {
        int preMove = len1 - len2;
        while(preMove --)
        {
            link1Idx = link1Idx -> next;
        }
    }
    else
    {
        int preMove = len2 - len1;
        while(preMove --)
        {
            link2Idx = link2Idx -> next;
        }

    }

    while(link1Idx != link2Idx)
    {
        link1Idx = link1Idx -> next;
        link2Idx = link2Idx -> next;
    }
    
    std::cout << "The cross point is " << link1Idx -> data << std::endl;
    return link1Idx;
}

void LinkOperation()
{   
    LinkNode * loopLink = generateLink(30);
    LinkNode * linkIdx = loopLink;
    LinkNode * crossNode = NULL;

    int length = 0;
    //link1Idx points to last element.
    //The 8th node is the cross Node
    while(linkIdx != NULL && linkIdx -> next != NULL)
    {
        if(length == 7)
            crossNode = linkIdx;
        std::cout << linkIdx -> data << "  ";
        linkIdx = linkIdx->next;
        length++;
    }
    length++;
    std::cout << linkIdx -> data << "  ";
    
    //build the loop link with cross node equals crossNode.
    //Whether to build loop link here.
    linkIdx->next = crossNode;
    std::cout << std::endl << "Expected the crossNode is " << crossNode -> data << std::endl;
    
    getIntersectNode(loopLink);
#if 0
    LinkNode * myLink = generateLink(30);
    LinkNode * cur = myLink;
    int count = 0;
    while(cur != NULL)
    {
        std::cout << cur->data << "  ";
        count ++;
        cur = cur->next;
    }

    std::cout << "Link length is " << count << std::endl;
#endif
    //构造后四个元素是交叉在一起的两个双向链表,一个长度是30, 一个是17+4 .
    //判断两条链表的交叉点.

#if 0
    LinkNode * longLink = generateLink(30);
    LinkNode * shortLink = generateLink(17);

    LinkNode * longIdx = longLink;
    LinkNode * shortIdx = shortLink;

    while(shortIdx != NULL && shortIdx -> next != NULL)
    {
        shortIdx = shortIdx->next;
    }

    int len = 26;
    while(len --)
    {
        longIdx = longIdx -> next;
    }

    shortIdx->next = longIdx;
    /////////////////////////////////////////////
    
    LinkNode * cur = longLink;
    int count = 0;
    while(cur != NULL)
    {
        std::cout << cur->data << "  ";
        count ++;
        cur = cur->next;
    }
    std::cout << std::endl<< "Long Link length is " << count << std::endl;


    cur = shortLink;
    count = 0;
    while(cur != NULL)
    {
        std::cout << cur->data << "  ";
        count ++;
        cur = cur->next;
    }
    std::cout << std::endl<< "Short Link length is " << count << std::endl;

    //This is the test code begin.
    getIntersectNode(longLink, shortLink);
#endif
}
